import com.sun.source.tree.Tree;

import java.util.*;

public class Solution {
    class TreeNode{
        int val;
        TreeNode left;
        TreeNode right;

        public TreeNode() {
        }

        public TreeNode(int val) {
            this.val = val;
        }
    }

    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> ans = new ArrayList<>();
        if(root == null){
            return ans;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.add(root);
        while(!stack.isEmpty()){
            TreeNode tmp = stack.pop();
            ans.add(tmp.val);
            if(tmp.right != null){
                stack.add(tmp.right);
            }
            if(tmp.left != null){
                stack.add(tmp.left);
            }
        }
        return ans;
    }

    public TreeNode buildTree1(int[] inorder, int[] postorder) {
        if(postorder.length == 0){
            return null;
        }

        int n = postorder.length;
        int endValue = postorder[n - 1];
        TreeNode root = new TreeNode(endValue);
        int index = 0;
        for(int i = 0; i < n; i++){
            if(endValue == inorder[i]){
                index = i;
                break;
            }
        }

        int[] leftInorder = Arrays.copyOfRange(inorder, 0, index);
        int[] leftPostorder = Arrays.copyOfRange(postorder, 0, leftInorder.length);
        root.left = buildTree1(leftInorder, leftPostorder);

        int[] rightInorder = Arrays.copyOfRange(inorder, index + 1, n);
//        for(int e : rightInorder) {
//            System.out.print(e + " ");
//        }
//        System.out.println();
        int[] rightPostorder = Arrays.copyOfRange(postorder, leftPostorder.length, n - 1);
//        for(int e : rightPostorder) {
//            System.out.print(e + " ");
//        }
//        System.out.println();
        root.right = buildTree1(rightInorder, rightPostorder);

        return root;
    }

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null){
            return null;
        }
        if(root == p || root == q){
            return root;
        }

        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);

        if(left != null && right != null){
            return root;
        }
        if(left != null){
            System.out.println(left.val);
            return left;
        }
        if(right != null){
            return right;
        }

        return null;
    }

    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        List<List<Integer>> ans = new LinkedList<>();
        if(root == null){
            return ans;
        }
        List<Integer> tmp = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while(!queue.isEmpty()){
            int sz = queue.size();
            for(int i = 0; i < sz; i++){
                TreeNode cur = queue.poll();
                tmp.add(cur.val);
                if(cur.left != null) queue.add(cur.left);
                if(cur.right != null) queue.add(cur.right);
            }
            ((LinkedList)ans).addFirst(new LinkedList<>(tmp));
            tmp.clear();
        }
        return ans;
    }

    public String tree2str(TreeNode root) {
        StringBuilder s = new StringBuilder();
        s.append(root.val);
        if(root.left == null && root.right == null){
            return s.toString();
        }
        s.append('(');
        if(root.left != null){
            s.append(tree2str(root.left));
        }
        if(root.left != null){
            s.append(tree2str(root.right));
        }
        s.append(')');
        return s.toString();
    }

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if(preorder.length == 0){
            return null;
        }
        int rootValue = preorder[0];
        TreeNode root = new TreeNode(rootValue);
        int index = 0;
        int n = inorder.length;
        for(int i = 0; i < n; i++){
            if(rootValue == inorder[i]){
                index = i;
                break;
            }
        }
        int[] leftInorder = Arrays.copyOfRange(inorder, 0, index);
        //System.out.println("length: " + leftInorder.length);


        int[] rightInorder = Arrays.copyOfRange(inorder, index + 1, n);
        int[] leftPreorder = Arrays.copyOfRange(preorder, 1, leftInorder.length + 1);
//        for(int e : leftPreorder){
//            System.out.print(e + " ");
//        }
//        System.out.println();
        int[] rightPreorder = Arrays.copyOfRange(preorder, 1 + leftPreorder.length, n);
//        for(int e : rightPreorder){
//            System.out.print(e + " ");
//        }
//        System.out.println();

        root.left = buildTree(leftPreorder, leftInorder);
        root.right = buildTree(rightPreorder, rightInorder);
        return root;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int []perorder = new int[]{3,9,20,15,7};
        int[] inorder = new int[]{9,3,15,20,7};
        solution.buildTree(perorder, inorder);
    }

}
